We give a development of the ODE method for the analysis of recursivealgorithms described by a stochastic recursion. With variability modelled viaan underlying Markov process, and under general assumptions, the followingresults are obtained: 1. Stability of an associated ODE implies that thestochastic recursion is stable in a strong sense when a gain parameter issmall. 2. The range of gain-values is quantified through a spectral analysis ofan associated linear operator, providing a non-local theory. 3. A second-orderanalysis shows precisely how variability leads to sensitivity of the algorithmwith respect to the gain parameter. All results are obtained within the natural operator-theoretic framework ofgeometrically ergodic Markov processes.
展开▼
